package com.aqie.hard.unionFind;

import java.util.*;

/**
 * 128 最长连续序列 todo
 */
public class LongestConsecutive {
    /**
     * 1. 排序 O(NlogN) 5ms
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        Arrays.sort(nums);

        int longestStreak = 1;
        int currentStreak = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                if (nums[i] == nums[i-1]+1) {
                    currentStreak += 1;
                }
                else {
                    longestStreak = Math.max(longestStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }

        return Math.max(longestStreak, currentStreak);
    }

    /**
     * O(N) 15ms
     * @param nums
     * @return
     */
    public int longestConsecutive2(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }

    /**
     * 并查集 18ms
     * @param nums
     * @return
     */
    public int longestConsecutive3(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res=0;
        for (int num:nums){
            if (map.containsKey(num)){
                continue;
            }
            int left = map.getOrDefault(num - 1, 0);
            int right = map.getOrDefault(num + 1, 0);
            int len = left+right+1;
            res = Math.max(res, len);
            map.put(num, 1);  //随便赋值,标记num在map中已存在
            map.put(num-left, len);  //左边端点
            map.put(num+right, len); //右边端点
        }
        return res;
    }


    public static void main(String[] args) {
        int[] arr = {100, 4, 200, 1, 3, 2};

    }
}
